import java.util.HashMap;
import java.util.Map;

/**
 * 1171. 从链表中删去总和值为零的连续节点
 * https://leetcode-cn.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/
 */
public class Solutions_1171 {
    public static void main(String[] args) {
        int[] arr = {1, 2, -3, 3, 1};  // output: {3, 1} or {1, 2, 1}
//        int[] arr = {1, 2, 3, -3, 4};  // output: {1, 2, 4}
//        int[] arr = {1, 2, 3, -3, -2};  // output: {1}
//        int[] arr = {1, -1};  // output: {}

        ListNode head = MyLinkedListUtils.ArrayToListNode(arr);
        ListNode result = removeZeroSumSublists(head);
        System.out.println(MyLinkedListUtils.ListNodeToString(result));
    }

    /**
     * 解题思路：前缀和
     */
    public static ListNode removeZeroSumSublists(ListNode head) {
        // 建立虚拟头结点（值为 0）
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        Map<Integer, ListNode> map = new HashMap<>();
        int sum = 0;
        // 记录前缀和
        for (ListNode node = dummy; node != null; node = node.next) {
            sum += node.val;
            map.put(sum, node);
        }
        sum = 0;
        for (ListNode node = dummy; node != null; node = node.next) {
            sum += node.val;
            // node.next 到 map.get(sum) 节点的和一定为 0
            // 那么删除和为 0 的区间，即将 node.next 指向 map.get(sum) 的下一节点
            node.next = map.get(sum).next;
        }
        return dummy.next;
    }
}
